/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 08 - 24
 * Time: 15:51
 */

class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                '}';
    }
}
//牛客 单链表的排序
public class Solution1 {
    public static ListNode sortInList (ListNode head) {
        return mergeSort(head, null);
    }
    private static ListNode mergeSort(ListNode head, ListNode end) {
        if(head == null) return null;
        if(head.next == end) {//注意这里是head.next==end
            head.next = null;
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast != end && fast.next != end) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode list1 = mergeSort(head, slow);
        ListNode list2 = mergeSort(slow, end);
        return merge(list1, list2);
    }
    private static ListNode merge(ListNode head1, ListNode head2) {
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while(head1 != null && head2 != null) {
            if(head1.val < head2.val) {
                cur.next = head1;
                cur = cur.next;
                head1 = head1.next;
            }else {
                cur.next = head2;
                cur = cur.next;
                head2 = head2.next;
            }
        }
        if(head1 != null) cur.next = head1;
        if(head2 != null) cur.next = head2;
        return head.next;
    }
}


